Temporary data buffering using a first-in-first-out (“FIFO”) or first-come-first-served (“FCFS”) device is commonly deployed in a digital computational environment. Upon receipt of data, FIFO device typically stores the data at a FIFO address indicated by a write-pointer. After the data is stored, the write-pointer is incremented to the next address, which points to the next storage location. To read data stored in the FIFO device, the data is read at a storage location pointed by a read-pointer. After the data is read, the read-pointer is incremented thereby the next read from the next storage location is properly pointed. The read and write pointers of the FIFO are basically counters that count data transfers. The counters are typically counting devices that wrap to zero when a maximum count is reached. Conventional binary-code counters are commonly used as FIFO pointers. When the read and write pointers are both operating within the same clock domain, the FIFO is known as a ‘synchronous’ FIFO. When they are in different clock domains, the FIFO is known as an ‘asynchronous’ FIFO.
The ‘full’ condition of the FIFO should be known by the write logic in order to avoid overwriting an unread entry. Similarly, the ‘empty’ condition of the FIFO should be known by the read logic in order to avoid reading an invalid entry. A logical comparison between the write-pointer and the read-pointer can typically determine the fill level of the FIFO. This operation poses some complications in ‘asynchronous’ FIFOs.
Since the read and write pointers in an asynchronous FIFO are in two independent clock domains, a direct comparison of the pointers would yield incorrect results. It is essential for both pointers to be in the same clock domain for the comparison to yield correct results. Therefore, each pointer needs to be ‘synchronized’ to the other pointer's clock domain. ‘Synchronization’ is a process of transferring signals from a given clock domain to a different clock domain to minimize metastability (an electrical condition that sets the underlying transistors in the circuit in an unknown (neither logic ‘1 ’ nor ‘0 ’) state).
The first step in synchronizing a signal that is generated in one clock domain (domain A) to another clock domain (domain B) is to sample the value of the signal in the target clock domain (domain B). When a value involving multiple signals (like a multi-bit binary count value) is sampled, there is a high probability of sampling the wrong value since the different bits making up the value may be toggling at different times. For example, when a counter increments from 011=3 to 100=4, every bit position changes. Such bit position changes may take place at slightly different times across each bit positions.
A conventional approach to alleviate or to reduce multiple bits changing scenario is to use Gray code instead of Binary code. Gray code typically requires a change in one bit position for every increment. For example, a 3-bit Gray code sequence is follows: 0=000, 1=001, 2=011, 3=010, 4=110, 5=111, 6=101, and 7=100. As such, Gray code provides a solution to reduce the ambiguities confronting binary code during cross-clock synchronization.
A problem associated with a Gray code counter is that it tends to break down for non-power-of-two counts. For instance, if a count of 6 values (non-power-of-two) is required, the simple Gray code sequence would be 000−>001−>011−>010−>110−>111 with the last value rolling back to 000. This would break the Gray coding rule of only one bit changing between adjacent values. Variations to Gray code have been proposed that accommodate non-power-of-two counts, but tend to be complex and is not readily scalable. Restricting FIFO designs to depths that are a power-of-two could be wasteful in terms of the memory size used. If, for example, a communication application only requires a FIFO depth of 80, the power-of-two counter requires 128 bits to address FIFO's 80 storage locations. The excess capacity can be costly in terms of integrated-circuit area that might otherwise be devoted to other functions.